home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 16 / CU Amiga Magazine's Super CD-ROM 16 (1997-10-16)(EMAP Images)(GB)[!][issue 1997-11].iso / CUCD / Graphics / Ghostscript / source / gxcpath.c < prev    next >
C/C++ Source or Header  |  1997-07-20  |  31KB  |  1,020 lines
  1. /* Copyright (C) 1991, 1995, 1996, 1997 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gxcpath.c */
  20. /* Implementation of clipping paths */
  21. #include "gx.h"
  22. #include "gserrors.h"
  23. #include "gsstruct.h"
  24. #include "gsutil.h"
  25. #include "gxdevice.h"
  26. #include "gxfixed.h"
  27. #include "gscoord.h"        /* needs gsmatrix.h */
  28. #include "gzpath.h"
  29. #include "gzcpath.h"
  30.  
  31. /* Define whether to look for vertical clipping regions. */
  32. #define CHECK_VERTICAL_CLIPPING
  33.  
  34. /* Imported from gxacpath.c */
  35. extern int gx_cpath_intersect_slow(P4(gs_state *, gx_clip_path *,
  36.   gx_path *, int));
  37.  
  38. /* Forward references */
  39. private void gx_clip_list_from_rectangle(P2(gx_clip_list *, gs_fixed_rect *));
  40. private int gx_clip_list_add_to_path(P2(gx_clip_list *, gx_path *));
  41.  
  42. /* Structure types */
  43. public_st_clip_rect();
  44. private_st_clip_list();
  45. public_st_clip_path();
  46. public_st_device_clip();
  47.  
  48. /* GC procedures for gx_clip_path */
  49. #define cptr ((gx_clip_path *)vptr)
  50. private ENUM_PTRS_BEGIN(clip_path_enum_ptrs) ;
  51.     if ( index < st_clip_list_max_ptrs )
  52.       { gs_ptr_type_t ret = clip_list_enum_ptrs(&cptr->list, sizeof(cptr->list), index, pep);
  53.         if ( ret == 0 )    /* don't stop early */
  54.           ret = ptr_struct_type, *pep = 0;
  55.         return ret;
  56.       }
  57.     return (*st_path.enum_ptrs)(&cptr->path, sizeof(cptr->path), index - st_clip_list_max_ptrs, pep);
  58. ENUM_PTRS_END
  59. private RELOC_PTRS_BEGIN(clip_path_reloc_ptrs) {
  60.     clip_list_reloc_ptrs(&cptr->list, sizeof(gx_clip_list), gcst);
  61.     (*st_path.reloc_ptrs)(&cptr->path, sizeof(gx_path), gcst);
  62. } RELOC_PTRS_END
  63. #undef cptr
  64.  
  65. /* GC procedures for gx_device_clip */
  66. #define cptr ((gx_device_clip *)vptr)
  67. private ENUM_PTRS_BEGIN(device_clip_enum_ptrs) {
  68.     if ( index < st_clip_list_max_ptrs + 1 )
  69.       return clip_list_enum_ptrs(&cptr->list, sizeof(gx_clip_list),
  70.                      index - 1, pep);
  71.     return (*st_device_forward.enum_ptrs)(vptr, sizeof(gx_device_forward),
  72.                           index - (st_clip_list_max_ptrs + 1), pep);
  73.     }
  74.     case 0:
  75.       ENUM_RETURN((cptr->current == &cptr->list.single ? NULL :
  76.                (void *)cptr->current));
  77. ENUM_PTRS_END
  78. private RELOC_PTRS_BEGIN(device_clip_reloc_ptrs) {
  79.     if ( cptr->current == &cptr->list.single )
  80.       cptr->current =
  81.         &((gx_device_clip *)gs_reloc_struct_ptr(vptr, gcst))->list.single;
  82.     else
  83.       RELOC_PTR(gx_device_clip, current);
  84.     clip_list_reloc_ptrs(&cptr->list, sizeof(gx_clip_list), gcst);
  85.     (*st_device_forward.reloc_ptrs)(vptr, sizeof(gx_device_forward), gcst);
  86. } RELOC_PTRS_END
  87. #undef cptr
  88.  
  89. /* Define an empty clip list. */
  90. private const gx_clip_list clip_list_empty =
  91. {  { 0, 0, min_int, max_int, 0, 0 },
  92.    0, 0, 0, 0 /*false*/
  93. };
  94.  
  95. /* Debugging */
  96.  
  97. #ifdef DEBUG
  98. /* Validate a clipping path. */
  99. bool        /* only exported for gxacpath.c */
  100. clip_list_validate(const gx_clip_list *clp)
  101. {    if ( clp->count <= 1 )
  102.       return (clp->head == 0 && clp->tail == 0 &&
  103.           clp->single.next == 0 && clp->single.prev == 0);
  104.     else
  105.       {    const gx_clip_rect *prev = clp->head;
  106.         const gx_clip_rect *ptr;
  107.         bool ok = true;
  108.         while ( (ptr = prev->next) != 0 )
  109.           { if ( ptr->ymin > ptr->ymax || ptr->xmin > ptr->xmax ||
  110.              !(ptr->ymin >= prev->ymax ||
  111.                (ptr->ymin == prev->ymin &&
  112.                 ptr->ymax == prev->ymax &&
  113.                 ptr->xmin >= prev->xmax)) ||
  114.              ptr->prev != prev
  115.                )
  116.               { clip_rect_print('q', "WRONG:", ptr);
  117.             ok = false;
  118.               }
  119.             prev = ptr;
  120.           }
  121.         return ok && prev == clp->tail;
  122.       }
  123. }
  124. #endif
  125.  
  126. /* ------ Clipping path accessing ------ */
  127.  
  128. /* Return the path of a clipping path. */
  129. int
  130. gx_cpath_path(gx_clip_path *pcpath, gx_path *ppath)
  131. {    if ( !pcpath->segments_valid )
  132.     {    int code;
  133.  
  134.         gx_path_reset(&pcpath->path);
  135.         code = gx_clip_list_add_to_path(&pcpath->list, &pcpath->path);
  136.         if ( code < 0 )
  137.           return code;
  138.         pcpath->segments_valid = 1;
  139.     }
  140.     *ppath = pcpath->path;
  141.     return 0;
  142. }
  143.  
  144. /* Return the inner and outer check rectangles for a clipping path. */
  145. /* Return true iff the path is a rectangle. */
  146. /* Note that these must return something strange if we are using */
  147. /* outside clipping. */
  148. bool
  149. gx_cpath_inner_box(const gx_clip_path *pcpath, gs_fixed_rect *pbox)
  150. {    if ( pcpath->list.outside )
  151.       { pbox->p.x = pbox->p.y = pbox->q.x = pbox->q.y = 0;
  152.         return false;
  153.       }
  154.     else
  155.       { *pbox = pcpath->inner_box;
  156.         return clip_list_is_rectangle(&pcpath->list);
  157.       }
  158. }
  159. bool
  160. gx_cpath_outer_box(const gx_clip_path *pcpath, gs_fixed_rect *pbox)
  161. {    if ( pcpath->list.outside )
  162.       { pbox->p.x = pbox->p.y = min_fixed;
  163.         pbox->q.x = pbox->q.y = max_fixed;
  164.         return false;
  165.       }
  166.     else
  167.       { *pbox = pcpath->outer_box;
  168.         return clip_list_is_rectangle(&pcpath->list);
  169.       }
  170. }
  171.  
  172. /* Test if a clipping path includes a rectangle. */
  173. /* The rectangle need not be oriented correctly, i.e. x0 > x1 is OK. */
  174. bool
  175. gx_cpath_includes_rectangle(register const gx_clip_path *pcpath,
  176.   fixed x0, fixed y0, fixed x1, fixed y1)
  177. {    return
  178.       (x0 <= x1 ?
  179.         (pcpath->inner_box.p.x <= x0 && x1 <= pcpath->inner_box.q.x) :
  180.         (pcpath->inner_box.p.x <= x1 && x0 <= pcpath->inner_box.q.x)) &&
  181.       (y0 <= y1 ?
  182.         (pcpath->inner_box.p.y <= y0 && y1 <= pcpath->inner_box.q.y) :
  183.         (pcpath->inner_box.p.y <= y1 && y0 <= pcpath->inner_box.q.y));
  184. }
  185.  
  186. /* Set the current outsideness of a clipping path. */
  187. int
  188. gx_cpath_set_outside(gx_clip_path *pcpath, bool outside)
  189. {    if ( outside != pcpath->list.outside )
  190.       { pcpath->id = gs_next_ids(1);    /* path changed => change id */
  191.         pcpath->list.outside = outside;
  192.       }
  193.     return 0;
  194. }
  195.  
  196. /* Return the current outsideness of a clipping path. */
  197. bool
  198. gx_cpath_is_outside(const gx_clip_path *pcpath)
  199. {    return pcpath->list.outside;
  200. }
  201.  
  202. /* Release a clipping path. */
  203. void
  204. gx_cpath_release(gx_clip_path *pcpath)
  205. {    if ( !pcpath->shares_list )
  206.         gx_clip_list_free(&pcpath->list, pcpath->path.memory);
  207.     gx_path_release(&pcpath->path);
  208. }
  209.  
  210. /* Share a clipping path. */
  211. void
  212. gx_cpath_share(gx_clip_path *pcpath)
  213. {    gx_path_share(&pcpath->path);
  214.     pcpath->shares_list = 1;
  215. }
  216.  
  217. /* Set the outer clipping box to the path bounding box, */
  218. /* expanded to pixel boundaries. */
  219. void
  220. gx_cpath_set_outer_box(gx_clip_path *pcpath)
  221. {    pcpath->outer_box.p.x = fixed_floor(pcpath->path.bbox.p.x);
  222.     pcpath->outer_box.p.y = fixed_floor(pcpath->path.bbox.p.y);
  223.     pcpath->outer_box.q.x = fixed_ceiling(pcpath->path.bbox.q.x);
  224.     pcpath->outer_box.q.y = fixed_ceiling(pcpath->path.bbox.q.y);
  225. }
  226.  
  227. /* ------ Clipping path setting ------ */
  228.  
  229. /* Initialize a clipping path. */
  230. int
  231. gx_cpath_init(gx_clip_path *pcpath, gs_memory_t *mem)
  232. {    static /*const*/ gs_fixed_rect null_rect = { { 0, 0 }, { 0, 0 } };
  233.     return gx_cpath_from_rectangle(pcpath, &null_rect, mem); /* does a gx_path_init */
  234. }
  235.  
  236. /* Create a rectangular clipping path. */
  237. /* The supplied rectangle may not be oriented correctly, */
  238. /* but it will be oriented correctly upon return. */
  239. int
  240. gx_cpath_from_rectangle(gx_clip_path *pcpath, gs_fixed_rect *pbox,
  241.   gs_memory_t *mem)
  242. {    gx_clip_list_from_rectangle(&pcpath->list, pbox);
  243.     pcpath->inner_box = *pbox;
  244.     pcpath->segments_valid = 0;
  245.     pcpath->shares_list = 0;
  246.     gx_path_init(&pcpath->path, mem);
  247.     pcpath->path.bbox = *pbox;
  248.     gx_cpath_set_outer_box(pcpath);
  249.     pcpath->id = gs_next_ids(1);    /* path changed => change id */
  250.     return 0;
  251. }
  252.  
  253. /* Intersect a new clipping path with an old one. */
  254. /* Note that it may overwrite its path argument; return 1 in this case, */
  255. /* otherwise 0 for success, <0 for failure as usual. */
  256. int
  257. gx_cpath_intersect(gs_state *pgs, gx_clip_path *pcpath, gx_path *ppath,
  258.   int rule)
  259. {    gs_fixed_rect old_box, new_box;
  260.     int code;
  261.  
  262.     if ( gx_cpath_inner_box(pcpath, &old_box) &&
  263.          ((code = gx_path_is_rectangle(ppath, &new_box)) ||
  264.           gx_path_is_void(ppath))
  265.        )
  266.        {    bool changed = false;
  267.         bool outside = pcpath->list.outside;
  268.  
  269.         if ( !code )
  270.           { /* The new path is void. */
  271.             if ( gx_path_current_point(ppath, &new_box.p) < 0 )
  272.               { /* Use the user space origin (arbitrarily). */
  273.             gs_point origin;
  274.  
  275.             gs_transform(pgs, 0.0, 0.0, &origin);
  276.             new_box.p.x = float2fixed(origin.x);
  277.             new_box.p.y = float2fixed(origin.y);
  278.                 gx_path_add_point(ppath, new_box.p.x, new_box.p.y);
  279.               }
  280.             new_box.q = new_box.p;
  281.           }
  282.         else
  283.           { /* Intersect the two rectangles if necessary. */
  284.             if ( old_box.p.x > new_box.p.x )
  285.               new_box.p.x = old_box.p.x, changed = true;
  286.             if ( old_box.p.y > new_box.p.y )
  287.               new_box.p.y = old_box.p.y, changed = true;
  288.             if ( old_box.q.x < new_box.q.x )
  289.               new_box.q.x = old_box.q.x, changed = true;
  290.             if ( old_box.q.y < new_box.q.y )
  291.               new_box.q.y = old_box.q.y, changed = true;
  292.             /* Check for a degenerate rectangle. */
  293.             if ( new_box.q.x < new_box.p.x )
  294.               new_box.q.x = new_box.p.x;
  295.             if ( new_box.q.y < new_box.p.y )
  296.               new_box.q.y = new_box.p.y;
  297.             if ( changed )
  298.               { /* Store the new rectangle back into the new path. */
  299.             register segment *pseg =
  300.               (segment *)ppath->first_subpath;
  301. #define set_pt(pqx,pqy)\
  302.   pseg->pt.x = new_box.pqx.x, pseg->pt.y = new_box.pqy.y
  303.             set_pt(p, p); pseg = pseg->next;
  304.             set_pt(q, p); pseg = pseg->next;
  305.             set_pt(q, q); pseg = pseg->next;
  306.             set_pt(p, q); pseg = pseg->next;
  307.             if ( pseg != 0 ) /* might be an open rectangle */
  308.               set_pt(p, p);
  309. #undef set_pt
  310.               }
  311.           }
  312.         ppath->bbox = new_box;
  313.         gx_cpath_release(pcpath);
  314.         gx_clip_list_from_rectangle(&pcpath->list, &new_box);
  315.         pcpath->list.outside = outside;
  316.         pcpath->inner_box = new_box;
  317.         pcpath->path = *ppath;
  318.         gx_cpath_set_outer_box(pcpath);
  319.         pcpath->segments_valid = 1;
  320.         pcpath->shares_list = 0;
  321.         code = 1;
  322.         pcpath->id = gs_next_ids(1);    /* path changed => change id */
  323.        }
  324.     else
  325.        {    /* Not a rectangle.  Intersect the slow way. */
  326.         code = gx_cpath_intersect_slow(pgs, pcpath, ppath, rule);
  327.        }
  328.     return code;
  329. }
  330.  
  331. /* Scale a clipping path by a power of 2. */
  332. int
  333. gx_cpath_scale_exp2(gx_clip_path *pcpath, int log2_scale_x, int log2_scale_y)
  334. {    int code =
  335.       gx_path_scale_exp2(&pcpath->path, log2_scale_x, log2_scale_y);
  336.     gx_clip_rect *pr;
  337.     if ( code < 0 )
  338.       return code;
  339.     /* Scale the fixed entries. */
  340.     gx_rect_scale_exp2(&pcpath->inner_box, log2_scale_x, log2_scale_y);
  341.     gx_rect_scale_exp2(&pcpath->outer_box, log2_scale_x, log2_scale_y);
  342.     /* Scale the clipping list. */
  343.     pr = pcpath->list.head;
  344.     if ( pr == 0 )
  345.       pr = &pcpath->list.single;
  346.     for ( ; pr != 0; pr = pr->next )
  347.       if ( pr != pcpath->list.head && pr != pcpath->list.tail )
  348.         {
  349. #define scale_v(v, s)\
  350.   if ( pr->v != min_int && pr->v != max_int )\
  351.     pr->v = (s >= 0 ? pr->v << s : pr->v >> -s)
  352.         scale_v(xmin, log2_scale_x);
  353.         scale_v(xmax, log2_scale_x);
  354.         scale_v(ymin, log2_scale_y);
  355.         scale_v(ymax, log2_scale_y);
  356. #undef scale_v
  357.         }
  358.     pcpath->id = gs_next_ids(1);    /* path changed => change id */
  359.     return 0;
  360. }
  361.  
  362. /* ------ Clipping list routines ------ */
  363.  
  364. /* Initialize a clip list. */
  365. void
  366. gx_clip_list_init(gx_clip_list *clp)
  367. {    *clp = clip_list_empty;
  368. }
  369.  
  370. /* Initialize a clip list to a rectangle. */
  371. /* The supplied rectangle may not be oriented correctly, */
  372. /* but it will be oriented correctly upon return. */
  373. private void
  374. gx_clip_list_from_rectangle(register gx_clip_list *clp,
  375.   register gs_fixed_rect *rp)
  376. {    gx_clip_list_init(clp);
  377.     if ( rp->p.x > rp->q.x )
  378.       { fixed t = rp->p.x; rp->p.x = rp->q.x; rp->q.x = t; }
  379.     if ( rp->p.y > rp->q.y )
  380.       { fixed t = rp->p.y; rp->p.y = rp->q.y; rp->q.y = t; }
  381.     clp->single.xmin = fixed2int_var(rp->p.x);
  382.     clp->single.ymin = fixed2int_var(rp->p.y);
  383.     clp->single.xmax = fixed2int_var_ceiling(rp->q.x);
  384.     clp->single.ymax = fixed2int_var_ceiling(rp->q.y);
  385.     clp->count = 1;
  386.     clp->outside = false;
  387. }
  388.  
  389. /* Add a clip list to a path. */
  390. /* In general, this produces a path made up of zillions of tiny lines. */
  391. private int
  392. gx_clip_list_add_to_path(gx_clip_list *clp, gx_path *ppath)
  393. {    gx_clip_rect *rp;
  394.     int code = -1;
  395.     gx_clip_rect *head = (clp->count <= 1 ? &clp->single : clp->head);
  396.     gx_clip_rect *visit;
  397.     gx_clip_rect *look;
  398.     enum { visit_left = 1, visit_right = 2 } first_visit;
  399.  
  400.     for ( rp = head; rp != 0; rp = rp->next )
  401.       if ( rp->xmin < rp->xmax && rp->ymin < rp->ymax )
  402.         rp->to_visit = visit_left | visit_right;
  403.     for ( visit = head; visit != 0; visit = visit->next )
  404.       { if ( !visit->to_visit )
  405.           continue;
  406.         rp = visit;
  407.         if ( visit->to_visit & visit_left )
  408.           { code = gx_path_add_point(ppath, int2fixed(visit->xmin),
  409.                      int2fixed(visit->ymax));
  410.             if ( code < 0 )
  411.           return code;
  412.         first_visit = visit_left;
  413.         goto left;
  414.           }
  415.         else
  416.           { code = gx_path_add_point(ppath, int2fixed(visit->xmax),
  417.                      int2fixed(visit->ymin));
  418.             if ( code < 0 )
  419.           return code;
  420.         first_visit = visit_right;
  421.         goto right;
  422.           }
  423. #define trace_line(px, py)\
  424.   code = gx_path_add_line(ppath, int2fixed(px), int2fixed(py));\
  425.   if ( code < 0 ) return code
  426. left:        /* Trace upward along a left edge. */
  427.         /* We're at the upper left corner of rp. */
  428.         rp->to_visit &= ~visit_left;
  429.         /* Look for an adjacent rectangle above rp. */
  430.         for ( look = rp;
  431.           (look = look->next) != 0 &&
  432.             (look->ymin == rp->ymin ||
  433.              (look->ymin == rp->ymax && look->xmax <= rp->xmin));
  434.         )
  435.           ;
  436.         /* Now we know look->ymin >= rp->ymax. */
  437.         if ( look == 0 || look->ymin > rp->ymax || look->xmin >= rp->xmax )
  438.           { /* No adjacent rectangle, switch directions. */
  439.         trace_line(rp->xmax, rp->ymax);
  440.         if ( rp == visit && first_visit == visit_right )
  441.           goto close;
  442.         goto right1;
  443.           }
  444.         /* We found an adjacent rectangle. */
  445.         /* See if it also adjoins a rectangle to the left of rp. */
  446.         { gx_clip_rect *prev = rp->prev;
  447.           if ( prev->ymax == rp->ymax && look->xmin < prev->xmax )
  448.         { /* There's an adjoining rectangle as well. */
  449.           /* Switch directions. */
  450.           trace_line(prev->xmax, rp->ymax);
  451.           rp = prev;
  452.           if ( rp == visit && first_visit == visit_right )
  453.             goto close;
  454.           goto right1;
  455.         }
  456.         }
  457.         trace_line(look->xmin, look->ymin);
  458.         rp = look;
  459.         if ( rp == visit && first_visit == visit_left )
  460.           goto close;
  461. left1:        trace_line(rp->xmin, rp->ymax);
  462.         goto left;
  463. right:        /* Trace downward along a right edge. */
  464.         /* We're at the lower right corner of rp. */
  465.         rp->to_visit &= ~visit_right;
  466.         /* Look for an adjacent rectangle below rp. */
  467.         for ( look = rp;
  468.           (look = look->prev) != 0 &&
  469.             (look->ymax == rp->ymax ||
  470.              (look->ymax == rp->ymin && look->xmin >= rp->xmax));
  471.         )
  472.           ;
  473.         /* Now we know look->ymax <= rp->ymin. */
  474.         if ( look == 0 || look->ymax < rp->ymin || look->xmax <= rp->xmin )
  475.           { /* No adjacent rectangle, switch directions. */
  476.         trace_line(rp->xmin, rp->ymin);
  477.         if ( rp == visit && first_visit == visit_left )
  478.           goto close;
  479.         goto left1;
  480.           }
  481.         /* We found an adjacent rectangle. */
  482.         /* See if it also adjoins a rectangle to the right of rp. */
  483.         { gx_clip_rect *next = rp->next;
  484.           if ( next->ymin == rp->ymin && look->xmax > next->xmin )
  485.         { /* There's an adjoining rectangle as well. */
  486.           /* Switch directions. */
  487.           trace_line(next->xmin, rp->ymin);
  488.           rp = next;
  489.           if ( rp == visit && first_visit == visit_left )
  490.             goto close;
  491.           goto left1;
  492.         }
  493.         }
  494.         trace_line(look->xmax, look->ymax);
  495.         rp = look;
  496.         if ( rp == visit && first_visit == visit_right )
  497.           goto close;
  498. right1:        trace_line(rp->xmax, rp->ymin);
  499.         goto right;
  500. close:        /* We've gone all the way around an edge. */
  501.         code = gx_path_close_subpath(ppath);
  502.         if ( code < 0 )
  503.           return code;
  504.       }
  505. #undef trace_line
  506.     if ( code < 0 )
  507.     {    /* We didn't have any rectangles. */
  508.         code = gx_path_add_point(ppath, fixed_0, fixed_0);
  509.     }
  510.     return code;
  511. }
  512.  
  513. /* Free a clip list. */
  514. void
  515. gx_clip_list_free(gx_clip_list *clp, gs_memory_t *mem)
  516. {    gx_clip_rect *rp = clp->tail;
  517.     while ( rp != 0 )
  518.     {    gx_clip_rect *prev = rp->prev;
  519.         gs_free_object(mem, rp, "gx_clip_list_free");
  520.         rp = prev;
  521.     }
  522.     gx_clip_list_init(clp);
  523. }
  524.  
  525. /* ------ Rectangle list clipper ------ */
  526.  
  527. /* Device for clipping with a region. */
  528. /* We forward non-drawing operations, but we must be sure to intercept */
  529. /* all drawing operations. */
  530. private dev_proc_open_device(clip_open);
  531. private dev_proc_fill_rectangle(clip_fill_rectangle);
  532. private dev_proc_copy_mono(clip_copy_mono);
  533. private dev_proc_copy_color(clip_copy_color);
  534. private dev_proc_get_bits(clip_get_bits);
  535. private dev_proc_copy_alpha(clip_copy_alpha);
  536. private dev_proc_fill_mask(clip_fill_mask);
  537. private dev_proc_strip_tile_rectangle(clip_strip_tile_rectangle);
  538. private dev_proc_strip_copy_rop(clip_strip_copy_rop);
  539. private dev_proc_get_clipping_box(clip_get_clipping_box);
  540.  
  541. /* The device descriptor. */
  542. private const gx_device_clip gs_clip_device =
  543. {    std_device_std_body(gx_device_clip, 0, "clipper",
  544.       0, 0, 1, 1),
  545.     {    clip_open,
  546.         gx_forward_get_initial_matrix,
  547.         gx_default_sync_output,
  548.         gx_default_output_page,
  549.         gx_default_close_device,
  550.         gx_forward_map_rgb_color,
  551.         gx_forward_map_color_rgb,
  552.         clip_fill_rectangle,
  553.         gx_default_tile_rectangle,
  554.         clip_copy_mono,
  555.         clip_copy_color,
  556.         gx_default_draw_line,
  557.         clip_get_bits,
  558.         gx_forward_get_params,
  559.         gx_forward_put_params,
  560.         gx_forward_map_cmyk_color,
  561.         gx_forward_get_xfont_procs,
  562.         gx_forward_get_xfont_device,
  563.         gx_forward_map_rgb_alpha_color,
  564.         gx_forward_get_page_device,
  565.         gx_forward_get_alpha_bits,
  566.         clip_copy_alpha,
  567.         gx_forward_get_band,
  568.         gx_default_copy_rop,
  569.         gx_default_fill_path,
  570.         gx_default_stroke_path,
  571.         clip_fill_mask,
  572.         gx_default_fill_trapezoid,
  573.         gx_default_fill_parallelogram,
  574.         gx_default_fill_triangle,
  575.         gx_default_draw_thin_line,
  576.         gx_default_begin_image,
  577.         gx_default_image_data,
  578.         gx_default_end_image,
  579.         clip_strip_tile_rectangle,
  580.         clip_strip_copy_rop,
  581.         clip_get_clipping_box
  582.     }
  583. };
  584. #define rdev ((gx_device_clip *)dev)
  585.  
  586. /* Make a clipping device. */
  587. void
  588. gx_make_clip_translate_device(gx_device_clip *dev, void *container,
  589.   const gx_clip_list *list, int tx, int ty)
  590. {    *dev = gs_clip_device;
  591.     dev->list = *list;
  592.     dev->translation.x = tx;
  593.     dev->translation.y = ty;
  594. }
  595. void
  596. gx_make_clip_path_device(gx_device_clip *dev, const gx_clip_path *pcpath)
  597. {    gx_make_clip_device(dev, NULL, &pcpath->list);
  598. }
  599.  
  600. /* Declare and initialize the cursor variables. */
  601. #ifdef DEBUG
  602. private ulong clip_loops, clip_in, clip_down, clip_up, clip_x, clip_no_x;
  603. private uint clip_interval = 10000;
  604. # define inc(v) v++
  605. # define print_clip()\
  606.     if ( clip_loops % clip_interval == 0 )\
  607.       if_debug10('q', "[q]rect=(%d,%d),(%d,%d)\n     loops=%ld in=%ld down=%ld up=%ld x=%ld no_x=%ld\n",\
  608.          x, y, x + w, y + h,\
  609.          clip_loops, clip_in, clip_down, clip_up, clip_x, clip_no_x)
  610. #else
  611. # define inc(v) discard(0)
  612. # define print_clip() DO_NOTHING
  613. #endif
  614. #define DECLARE_CLIP\
  615.   register gx_clip_rect *rptr = rdev->current;\
  616.   gx_device *tdev = rdev->target;\
  617.   bool outside = rdev->list.outside;
  618. /* Translate the supplied coordinates. */
  619. #define TRANSLATE_CLIP\
  620.   x += rdev->translation.x;\
  621.   y += rdev->translation.y;
  622. /* Check whether the rectangle x,y,w,h falls within the current entry. */
  623. #define xywh_is_in_ryptr()\
  624.   (!outside &&\
  625.    y >= rptr->ymin && y + h <= rptr->ymax &&\
  626.    x >= rptr->xmin && x + w <= rptr->xmax)
  627. #ifdef DEBUG
  628. #  define xywh_in_ryptr() (xywh_is_in_ryptr() ? (inc(clip_in), 1) : 0)
  629. #else
  630. #  define xywh_in_ryptr() xywh_is_in_ryptr()
  631. #endif
  632. /*
  633.  * Warp the cursor forward or backward to the first rectangle row that
  634.  * could include a given y value.  Assumes rptr is set, and updates it.
  635.  * Specifically, after warp_cursor, either rptr == 0 (if the y value is
  636.  * greater than all y values in the list), or y < rptr->ymax and either
  637.  * rptr->prev == 0 or y >= rptr->prev->ymax.  Note that y <= rptr->ymin
  638.  * is possible.
  639.  *
  640.  * In the first case below, the while loop is safe because if there is
  641.  * more than one rectangle, there is a 'stopper' at the end of the list.
  642.  */
  643. #define warp_cursor(y)\
  644.   if ( (y) >= rptr->ymax )\
  645.    { if ( (rptr = rptr->next) != 0 )\
  646.        while ( inc(clip_up), (y) >= rptr->ymax ) rptr = rptr->next;\
  647.    }\
  648.   else while ( rptr->prev != 0 && (y) < rptr->prev->ymax )\
  649.    { inc(clip_down); rptr = rptr->prev; }
  650. /*
  651.  * Enumerate the rectangles of the x,w,y,h argument that fall within
  652.  * the clipping region.  Usage:
  653.  *    DO_CLIP(adjust for yc > yp if necessary,
  654.  *        process(xc, yc, xec, yec) [must be an expression])
  655.  *
  656.  * Note that we look ahead to detect unclipped vertical strips.
  657.  * This is really only valuable for 90 degree rotated images or
  658.  * (nearly-)vertical lines with convex clipping regions; if we ever
  659.  * change images to use source buffering and destination-oriented
  660.  * enumeration, we could probably take out the code here with no
  661.  * adverse effects.
  662.  */
  663. #ifdef CHECK_VERTICAL_CLIPPING
  664. #  define LOOK_AHEAD\
  665.                 if ( xec - xc == w )    /* full width */\
  666.                   { /* Look ahead for a vertical swath. */\
  667.                     while ( (nptr = rptr->next) != 0 &&\
  668.                         nptr->ymin == yec &&\
  669.                         nptr->ymax <= ye &&\
  670.                         nptr->xmin <= x &&\
  671.                         nptr->xmax >= xe\
  672.                       )\
  673.                       yec = nptr->ymax, rptr = nptr;\
  674.                   }\
  675.                 else\
  676.                   nptr = rptr->next
  677. #else
  678. #  define LOOK_AHEAD\
  679.                   nptr = rptr->next
  680. #endif
  681. #define DO_CLIP(adjust_for_y, process_rectangle)\
  682.     if ( w <= 0 || h <= 0 ) return 0;\
  683.     inc(clip_loops);\
  684.     print_clip();\
  685.    {    const int xe = x + w, ye = y + h;\
  686.     int xc, xec, yc, yec, yp, yep;\
  687.     int code;\
  688. \
  689.     warp_cursor(y);\
  690.     if ( rptr == 0 || (yc = rptr->ymin) >= ye )\
  691.       { if ( rdev->list.count > 1 )\
  692.           rdev->current =\
  693.         (rptr != 0 ? rptr :\
  694.          y >= rdev->current->ymax ? rdev->list.tail :\
  695.          rdev->list.head);\
  696.         return (outside ? (xc = x, xec = xe, yc = y, yec = ye,\
  697.                    process_rectangle) : 0);\
  698.       }\
  699.     rdev->current = rptr;\
  700.     if ( yc < y ) yc = y;\
  701.     yp = y;\
  702.     if ( outside )\
  703.       { for ( yep = y; ; )\
  704.           { const int ymax = rptr->ymax;\
  705. \
  706.         xc = x;\
  707.         if ( yc > yep )\
  708.           { yec = yc, yc = yep;\
  709.             adjust_for_y;\
  710.             xec = xe;\
  711.             code = process_rectangle;\
  712.             if ( code < 0 ) return code;\
  713.             yp = yep;\
  714.             yc = yec;\
  715.             adjust_for_y;\
  716.           }\
  717.         yec = min(ymax, ye);\
  718.         do \
  719.            {    xec = rptr->xmin;\
  720.             if ( xec > xc )\
  721.                {    if ( xec > xe ) xec = xe;\
  722.                 code = process_rectangle;\
  723.                 if ( code < 0 ) return code;\
  724.                 xc = rptr->xmax;\
  725.                 if ( xc >= xe ) xc = max_int;\
  726.                }\
  727.             else\
  728.               { xec = rptr->xmax;\
  729.                 if ( xec > xc ) xc = xec;\
  730.               }\
  731.            }\
  732.         while ( (rptr = rptr->next) != 0 && rptr->ymax == ymax );\
  733.         if ( xc < xe )\
  734.           { xec = xe;\
  735.             code = process_rectangle;\
  736.             if ( code < 0 ) return code;\
  737.           }\
  738.         yp = yc;\
  739.         yep = yec;\
  740.         if ( rptr == 0 || (yc = rptr->ymin) >= ye ) break;\
  741.           }\
  742.         if ( yep < ye )\
  743.           { xc = x, xec = xe, yc = yep, yec = ye;\
  744.         code = process_rectangle;\
  745.         if ( code < 0 ) return code;\
  746.           }\
  747.       }\
  748.     else \
  749.       for ( ; ; )\
  750.         {    const int ymax = rptr->ymax;\
  751.         gx_clip_rect *nptr;\
  752. \
  753.         yec = min(ymax, ye);\
  754.         if ( yc > yp ) adjust_for_y;\
  755.         if_debug2('Q', "[Q]yc=%d yec=%d\n", yc, yec);\
  756.         do \
  757.            {    xc = rptr->xmin;\
  758.             xec = rptr->xmax;\
  759.             if ( xc < x ) xc = x;\
  760.             if ( xec > xe ) xec = xe;\
  761.             if ( xec > xc )\
  762.                {    clip_rect_print('Q', "match", rptr);\
  763.                 if_debug2('Q', "[Q]xc=%d xec=%d\n", xc, xec);\
  764.                 inc(clip_x);\
  765.                 LOOK_AHEAD;\
  766.                 code = process_rectangle;\
  767.                 if ( code < 0 ) return code;\
  768.                }\
  769.             else\
  770.               { inc(clip_no_x);\
  771.                 nptr = rptr->next;\
  772.               }\
  773.            }\
  774.         while ( (rptr = nptr) != 0 && rptr->ymax == ymax );\
  775.         if ( rptr == 0 || (yec = rptr->ymin) >= ye ) break;\
  776.         yp = yc;\
  777.         yc = yec;\
  778.         }\
  779.    }
  780.  
  781. /* Open a clipping device */
  782. private int
  783. clip_open(register gx_device *dev)
  784. {    gx_device *tdev = rdev->target;
  785.     /* Initialize the cursor. */
  786.     rdev->current =
  787.       (rdev->list.head == 0 ? &rdev->list.single : rdev->list.head);
  788.     rdev->color_info = tdev->color_info;
  789.     rdev->width = tdev->width;
  790.     rdev->height = tdev->height;
  791.     return 0;
  792. }
  793.  
  794. /* Fill a rectangle */
  795. private int
  796. clip_fill_rectangle(gx_device *dev, int x, int y, int w, int h,
  797.   gx_color_index color)
  798. {    DECLARE_CLIP
  799.     dev_proc_fill_rectangle((*fill)) = dev_proc(tdev, fill_rectangle);
  800.  
  801.     TRANSLATE_CLIP
  802.     if ( xywh_in_ryptr() )
  803.       return (*fill)(tdev, x, y, w, h, color);
  804.     DO_CLIP(DO_NOTHING,
  805.         (*fill)(tdev, xc, yc, xec - xc, yec - yc, color))
  806.     return 0;
  807. }
  808.  
  809. /* Copy a monochrome rectangle */
  810. private int
  811. clip_copy_mono(gx_device *dev,
  812.   const byte *data, int sourcex, int raster, gx_bitmap_id id,
  813.   int x, int y, int w, int h,
  814.   gx_color_index color0, gx_color_index color1)
  815. {    DECLARE_CLIP
  816.     dev_proc_copy_mono((*copy)) = dev_proc(tdev, copy_mono);
  817.  
  818.     TRANSLATE_CLIP
  819.     if ( xywh_in_ryptr() )
  820.       return (*copy)(tdev, data, sourcex, raster, id, x, y, w, h, color0, color1);
  821.     DO_CLIP(data += (yc - yp) * raster,
  822.         (*copy)(tdev, data, sourcex + xc - x, raster, gx_no_bitmap_id,
  823.             xc, yc, xec - xc, yec - yc, color0, color1))
  824.     return 0;
  825. }
  826.  
  827. /* Copy a color rectangle */
  828. private int
  829. clip_copy_color(gx_device *dev,
  830.   const byte *data, int sourcex, int raster, gx_bitmap_id id,
  831.   int x, int y, int w, int h)
  832. {    DECLARE_CLIP
  833.     dev_proc_copy_color((*copy)) = dev_proc(tdev, copy_color);
  834.  
  835.     TRANSLATE_CLIP
  836.     if ( xywh_in_ryptr() )
  837.       return (*copy)(tdev, data, sourcex, raster, id, x, y, w, h);
  838.     DO_CLIP(data += (yc - yp) * raster,
  839.         (*copy)(tdev, data, sourcex + xc - x, raster, gx_no_bitmap_id,
  840.             xc, yc, xec - xc, yec - yc))
  841.     return 0;
  842. }
  843.  
  844. /* Copy a rectangle with alpha */
  845. private int
  846. clip_copy_alpha(gx_device *dev,
  847.   const byte *data, int sourcex, int raster, gx_bitmap_id id,
  848.   int x, int y, int w, int h,
  849.   gx_color_index color, int depth)
  850. {    DECLARE_CLIP
  851.     dev_proc_copy_alpha((*copy)) = dev_proc(tdev, copy_alpha);
  852.  
  853.     TRANSLATE_CLIP
  854.     if ( xywh_in_ryptr() )
  855.       return (*copy)(tdev, data, sourcex, raster, id, x, y, w, h, color, depth);
  856.     DO_CLIP(data += (yc - yp) * raster,
  857.         (*copy)(tdev, data, sourcex + xc - x, raster, gx_no_bitmap_id,
  858.             xc, yc, xec - xc, yec - yc, color, depth))
  859.     return 0;
  860. }
  861.  
  862. /* Fill a region defined by a mask. */
  863. private int
  864. clip_fill_mask(gx_device *dev,
  865.   const byte *data, int sourcex, int raster, gx_bitmap_id id,
  866.   int x, int y, int w, int h,
  867.   const gx_drawing_color *pdcolor, int depth,
  868.   gs_logical_operation_t lop, const gx_clip_path *pcpath)
  869. {    DECLARE_CLIP
  870.     dev_proc_fill_mask((*fill)) = dev_proc(tdev, fill_mask);
  871.  
  872.     if ( pcpath != 0 )
  873.       return gx_default_fill_mask(dev, data, sourcex, raster, id,
  874.                       x, y, w, h, pdcolor, depth, lop,
  875.                       pcpath);
  876.     TRANSLATE_CLIP
  877.     if ( xywh_in_ryptr() )
  878.       return (*fill)(tdev, data, sourcex, raster, id, x, y, w, h,
  879.              pdcolor, depth, lop, NULL);
  880.     DO_CLIP(data += (yc - yp) * raster,
  881.         (*fill)(tdev, data, sourcex + xc - x, raster, gx_no_bitmap_id,
  882.             xc, yc, xec - xc, yec - yc, pdcolor, depth, lop,
  883.             NULL))
  884.     return 0;
  885. }
  886.  
  887. /* Get bits back from the device. */
  888. private int
  889. clip_get_bits(gx_device *dev, int y, byte *data, byte **actual_data)
  890. {    gx_device *tdev = rdev->target;
  891.     return (*dev_proc(tdev, get_bits))(tdev, y - rdev->translation.y,
  892.                        data, actual_data);
  893. }
  894.  
  895. /* Strip-tile a rectangle. */
  896. private int
  897. clip_strip_tile_rectangle(gx_device *dev, const gx_strip_bitmap *tiles,
  898.   int x, int y, int w, int h,
  899.   gx_color_index color0, gx_color_index color1, int phase_x, int phase_y)
  900. {    DECLARE_CLIP
  901.     dev_proc_strip_tile_rectangle((*fill)) =
  902.       dev_proc(tdev, strip_tile_rectangle);
  903.  
  904.     TRANSLATE_CLIP
  905.     if ( xywh_in_ryptr() )
  906.       return (*fill)(tdev, tiles, x, y, w, h, color0, color1, phase_x, phase_y);
  907.     DO_CLIP(DO_NOTHING,
  908.         (*fill)(tdev, tiles, xc, yc, xec - xc, yec - yc,
  909.             color0, color1, phase_x, phase_y))
  910.     return 0;
  911. }
  912.  
  913. /* Copy a rectangle with RasterOp and strip texture. */
  914. private int
  915. clip_strip_copy_rop(gx_device *dev,
  916.   const byte *sdata, int sourcex, uint raster, gx_bitmap_id id,
  917.   const gx_color_index *scolors,
  918.   const gx_strip_bitmap *textures, const gx_color_index *tcolors,
  919.   int x, int y, int w, int h,
  920.   int phase_x, int phase_y, gs_logical_operation_t lop)
  921. {    DECLARE_CLIP
  922.     dev_proc_strip_copy_rop((*copy)) = dev_proc(tdev, strip_copy_rop);
  923.  
  924.     TRANSLATE_CLIP
  925.     if ( xywh_in_ryptr() )
  926.       return (*copy)(tdev, sdata, sourcex, raster, id, scolors,
  927.              textures, tcolors, x, y, w, h,
  928.              phase_x, phase_y, lop);
  929.     DO_CLIP(sdata += (yc - yp) * raster,
  930.         (*copy)(tdev, sdata, sourcex + xc - x, raster,
  931.             gx_no_bitmap_id, scolors, textures, tcolors,
  932.             xc, yc, xec - xc, yec - yc,
  933.             phase_x, phase_y, lop))
  934.     return 0;
  935. }
  936.  
  937. /* Get the (outer) clipping box, in client coordinates. */
  938. private void
  939. clip_get_clipping_box(gx_device *dev, gs_fixed_rect *pbox)
  940. {    gx_device *tdev = rdev->target;
  941.     gs_fixed_rect tbox, cbox;
  942.     fixed tx = int2fixed(rdev->translation.x),
  943.       ty = int2fixed(rdev->translation.y);
  944.  
  945.     (*dev_proc(tdev, get_clipping_box))(tdev, &tbox);
  946.     /*
  947.      * To get an accurate clipping box quickly in all cases, we should
  948.      * save the outer box from the clipping path.  However,
  949.      * this is not currently (or even always guaranteed to be)
  950.      * available.  Instead, we compromise: if there is more than one
  951.      * rectangle in the list, we return accurate Y values (which are
  952.      * easy to obtain, because the list is Y-sorted) but copy the
  953.      * X values from the target.
  954.      */
  955.     if ( rdev->list.outside || rdev->list.count == 0 )
  956.       { cbox = tbox;
  957.       }
  958.     else if ( rdev->list.count == 1 )
  959.       { cbox.p.x = int2fixed(rdev->list.single.xmin);
  960.         cbox.p.y = int2fixed(rdev->list.single.ymin);
  961.         cbox.q.x = int2fixed(rdev->list.single.xmax);
  962.         cbox.q.y = int2fixed(rdev->list.single.ymax);
  963.       }
  964.     else
  965.       { /* The head and tail elements are dummies.... */
  966.         cbox.p.x = tbox.p.x;
  967.         cbox.p.y = int2fixed(rdev->list.head->next->ymin);
  968.         cbox.q.x = tbox.q.x;
  969.         cbox.q.y = int2fixed(rdev->list.tail->prev->ymax);
  970.       }
  971.     rect_intersect(tbox, cbox);
  972.     if ( tbox.p.x != min_fixed )
  973.       tbox.p.x -= tx;
  974.     if ( tbox.p.y != min_fixed )
  975.       tbox.p.y -= ty;
  976.     if ( tbox.q.x != max_fixed )
  977.       tbox.q.x -= tx;
  978.     if ( tbox.q.y != max_fixed )
  979.       tbox.q.y -= ty;
  980.     *pbox = tbox;
  981. }
  982.  
  983. /* ------ Debugging printout ------ */
  984.  
  985. #ifdef DEBUG
  986.  
  987. /* Print a clipping path */
  988. void
  989. gx_cpath_print(const gx_clip_path *pcpath)
  990. {    const gx_clip_rect *pr;
  991.     if ( pcpath->segments_valid )
  992.         gx_path_print(&pcpath->path);
  993.     else
  994.         dputs("   (segments not valid)\n");
  995.     dprintf4("   inner_box=(%g,%g),(%g,%g)\n",
  996.          fixed2float(pcpath->inner_box.p.x),
  997.          fixed2float(pcpath->inner_box.p.y),
  998.          fixed2float(pcpath->inner_box.q.x),
  999.          fixed2float(pcpath->inner_box.q.y));
  1000.     dprintf5("     outer_box=(%g,%g),(%g,%g) count=%d\n",
  1001.          fixed2float(pcpath->outer_box.p.x),
  1002.          fixed2float(pcpath->outer_box.p.y),
  1003.          fixed2float(pcpath->outer_box.q.x),
  1004.          fixed2float(pcpath->outer_box.q.y),
  1005.          pcpath->list.count);
  1006.     dprintf2("     rule=%d outside=%d\n",
  1007.          pcpath->rule, pcpath->list.outside);
  1008.     switch ( pcpath->list.count )
  1009.     {
  1010.     case 0: pr = 0; break;
  1011.     case 1: pr = &pcpath->list.single; break;
  1012.     default: pr = pcpath->list.head;
  1013.     }
  1014.     for ( ; pr != 0; pr = pr->next )
  1015.       dprintf4("   rect: (%d,%d),(%d,%d)\n",
  1016.            pr->xmin, pr->ymin, pr->xmax, pr->ymax);
  1017. }
  1018.  
  1019. #endif                    /* DEBUG */
  1020.